#ifndef DISTTREE_H_INCLUDED
#define DISTTREE_H_INCLUDED

#include<cstdlib>
#include<vector>
#include<cmath>
#include <algorithm>


template<typename dataType, typename Compare = std::less<dataType>>
class distTree
{
private:
    struct dist
    {
        size_t begin;
        size_t end;
        dataType min;
        dataType diff;

        dist(size_t newBegin = 0, size_t newEnd = 0, dataType newMin = dataType())
        {
            begin = newBegin;
            end = newEnd;
            min = newMin;
            diff = dataType();
        }
        dist(dataType val)
        {
            min = val;
            end = begin + 1;
        }
    };

    std::vector<dist> dists;
    size_t maxDeep;
    size_t size;
    size_t realSize;

    void push(size_t nmb, dataType updiff = dataType())
    {
        if (dists[nmb].diff == dataType() && updiff == dataType())
            return;
        if (nmb < size)
        {
            push(nmb*2 + 1, dists[nmb].diff + updiff);
            push(nmb*2 + 2, dists[nmb].diff + updiff);
            dists[nmb].min = std::min(dists[nmb*2 + 1].min, dists[nmb*2 + 1].min, Compare());
        }
        else
        {
            dists[nmb].min = dists[nmb].min + updiff + dists[nmb].diff;
        }
        dists[nmb].diff = dataType();
    }

    void resize(size_t newSize)
    {
        realSize = newSize;
        maxDeep = (size_t)ceil(log(1.0*newSize)/log(2));
        newSize = pow(2, maxDeep);
        size = newSize;
        dists.resize(2*newSize);
        size_t i = 0;
        size_t nowBegin = 0;
        size_t nowEnd = size;
        int nowSize = size;
        for (size_t i = 0; i < 2*size; ++i)
        {
            dists[i].begin = nowBegin;
            dists[i].end = nowEnd;
            dists[i].min = dataType();
            dists[i].diff = dataType();
            if (nowEnd == size)
            {
                nowSize = nowSize / 2;
                nowBegin = 0;
                nowEnd = nowBegin + nowSize;
            }
            else
            {
                nowBegin = nowBegin + nowSize;
                nowEnd = nowBegin + nowSize;
            }
        }
    }

public:

    distTree(size_t newSize)
    {
        resize(newSize);
    }


    size_t sizeArr()
    {
        return realSize;
    }

    class iterator : public std::iterator<std::random_access_iterator_tag, dataType>
    {
    private:
        dist* nowPos;
    public:
        iterator(dist* newPos)
        {
            nowPos = newPos;
        }
        iterator operator++(int)
        {
            ++nowPos;
            return *this;
        }
        iterator operator++()
        {
            nowPos++;
            return *this;
        }
        dataType operator*()
        {
            return (nowPos->min);
        }
        iterator operator+(ssize_t n)
        {
            nowPos = nowPos + n;
            return *this;
        }
        iterator operator+=(ssize_t n)
        {
            nowPos = nowPos + n;
            return *this;
        }
        ssize_t operator-(const iterator& other)
        {
            return (nowPos - other.nowPos);
        }
        bool operator==(const iterator& other)
        {
            return nowPos == other.nowPos;
        }
        bool operator!=(const iterator& other)
        {
            return !(*this == other);
        }
    };
    iterator beginArr()
    {
        return iterator(&(*(dists.begin() + size - 1)));
    }
    iterator endArr()
    {
        return iterator(&(*(dists.begin() + size - 1 + realSize)));
    }


    void change(size_t begin, size_t end, dataType value, size_t nmb = 0)
    {
        push(nmb);
        if (nmb >= 2*size - 1 || begin >= dists[nmb].end || end < dists[nmb].begin)
            return;
        if (nmb >= size - 1)
        {
            dists[nmb].diff = dataType();
            dists[nmb].min = dists[nmb].min + value;
            return;
        }

        if (begin <= dists[nmb].begin && end >= dists[nmb].end)
        {
            dists[nmb].diff = dists[nmb].diff + value;
            return;
        }

        if (begin <= dists[nmb].begin + (dists[nmb].end - dists[nmb].begin)/2)
            change(begin, end, value, nmb*2 + 1);
        if (end > dists[nmb].begin + (dists[nmb].end - dists[nmb].begin)/2)
            change(begin, end, value, nmb*2 + 2);
        if (dists[nmb].diff == dataType())
            dists[nmb].min = std::min(dists[nmb*2 + 1].min, dists[nmb*2 + 2].min, Compare());
    }

    dataType getMin(size_t begin, size_t end, size_t nmb = 0)
    {
        if (dists[nmb].diff != dataType())
            push(nmb);
        if (nmb >= size - 1 || (begin <= dists[nmb].begin && end >= dists[nmb].end))
        {
            return dists[nmb].min;
        }
        if (begin >= dists[nmb].begin + (dists[nmb].end - dists[nmb].begin)/2)
            return getMin(begin, end, nmb*2 + 2);
        if (end <= dists[nmb].begin + (dists[nmb].end - dists[nmb].begin)/2)
            return getMin(begin, end, nmb*2 + 1);
        return std::min(getMin(begin, end, nmb*2 + 2), getMin(begin, end, nmb*2 + 1), Compare());
    }

    distTree(const std::vector<dataType>& base)
    {
        resize(base.size());
        for (size_t i = 0; i < base.size(); ++i)
        {
            change(i, i + 1, base[i]);
        }
    }

    dataType operator[](size_t nmb)
    {
        return getMin(nmb, nmb + 1);
    }


};

#endif // DISTTREE_H_INCLUDED
